This estimator has been the subject of extensive empirical inquiry [e.g.

We prove that the true underlying directed acyclic graph (DAG) in Gaussian linear structural equation models is identifiable as the minimum-trace DAG when the error variances are weakly increasing with respect to the true causal ordering. This result bridges two existing frameworks as it extends the identifiable cases within the minimum-trace DAG method and provides a principled interpretation of the algorithmic ordering search approach, revealing that its objective is actually to minimize the total residual sum of squares. On the computational side, we prove that the hill climbing algorithm with a random-to-random (R2R) neighborhood does not admit any strict local optima. Under standard settings, we confirm the result through extensive simulations, observing only a few weak local optima. Interestingly, algorithms using other neighborhoods of equal size exhibit suboptimal behavior, having strict local optima and a substantial number of weak local optima.

Update: The authors gave a good rebuttal, I have increased my score to 6. Original comments: In this paper, the authors considered the problem of learning directed acyclic graphs via optimizing a score. In particular, they have developed a new approach that requires O(s log p) samples to learn a DAG from the data. The proposed a approach is an optimization based approach that learns a DAG via optimizing a nonconvex scoring function. The theoretical analysis of this paper is complete. In addition, the analysis techniques developed in this paper seems to be helpful to solve other related problems in structure learning and high-dimensional statistics.